package leetcode.editor.cn.q0xx

class Q74_Medium {
    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        val m = matrix.size
        val n = matrix[0].size
        var low = 0
        var high = m*n - 1
        do {
            val medium = (low + high) / 2
            val i = medium / n
            val j = medium % n
            when {
                matrix[i][j] < target -> {
                    low = medium + 1
                }
                matrix[i][j] > target -> {
                    high = medium - 1
                }
                else -> {
                    return true
                }
            }
        } while (low<=high)
        return false
    }
}

fun main(args: Array<String>) {
    val matrix = arrayOf(intArrayOf(1,3,5,7), intArrayOf(10,11,16,20), intArrayOf(23,30,34,60))
    println(Q74_Medium().searchMatrix(matrix, 21))
}